package tree;

import queue.Queue;

public class PaperFolding {
    public static void main(String[] args) {
        Node tree = createTree(2);
        printTree(tree);
    }

    private static void printTree(Node x){
        if (x == null){
            return;
        }
        if (x.left != null){
            printTree(x.left);
        }
        System.out.println(x.item);
        if (x.right != null){
            printTree(x.right);
        }
    }

    private static Node createTree(int N){
        Node root = null;
        for (int i = 0; i < N; i++) {
            if (i == 0){
                root = new Node("down",null,null);
                continue;
            }
            Queue<Node> queue = new Queue<>();
            queue.enqueue(root);
            while (!queue.isEmpty()){
                Node x = queue.dequeue();
                if (x.left != null){
                    queue.enqueue(x.left);
                }
                if (x.right != null){
                    queue.enqueue(x.right);
                }
                if (x.left == null && x.right == null){
                    x.left = new Node("down",null,null);
                    x.right = new Node("up",null,null);
                }
            }
        }
        return root;
    }
    public static class Node{
        String item;
        Node left;
        Node right;

        public Node(String item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}
